--算法工具

td.OrientationAll = {   [8]={ x = -1 , y = 1 },[1]={ x = 0 , y = 1 },[2]={ x = 1 , y = 1 },
                        [7]={ x = -1 , y = 0 },                      [3]={ x = 1 , y = 0 },
                        [6]={ x = -1 , y = -1},[5]={ x = 0 , y = -1},[4]={ x = 1 , y = -1},
                    }

td.OrientationOrder = { [0]={1,2,3,4,5,6,7,8},
                        [1]={1,2,3,8},
                        [2]={2,3,4,1},
                        [3]={3,4,5,2},
                        [4]={4,5,6,3},
                        [5]={5,6,7,4},
                        [6]={6,7,8,5},
                        [7]={7,8,1,6},
                        [8]={8,1,2,7},
}

function td.SeekNearestFor8( starPos , endPos , type)  --八方向最近格点判定：起点坐标（格点），终点坐标（格点），地图数据 搜索类型（1近战2远程） 返回最近的目标格子，该函数所有判定都用格点（Grid）
    --引用相关：  td.OrientationAll td.OrientationOrder
    local Map = Map or td.MapLayer.MapTable
    type = type or 1
    local deteal
    if type == 1 then 
        deteal = cc.pSub(starPos,endPos)
    elseif type == 2 then 
        deteal = cc.pSub(endPos,starPos)
    end
    
    --获取方向编号，后续可以修改方向顺序降低判断次数（已修改）
    local Orientation = 0

    if deteal.x == 0 then 
        if deteal.y > 0 then 
            Orientation = 1
        elseif deteal.y < 0 then 
            Orientation = 5
        end
    else
        local k = deteal.y/deteal.x 
        if deteal.x > 0 then
            if k > 1 then
                Orientation = 1
            elseif k <= 1 and k > 0 then
                Orientation = 2
            elseif k <= 0 and k > -1 then
                Orientation = 3
            elseif k <= -1 then
                Orientation = 4
            end
        elseif deteal.x < 0 then   
            if k >1 then
                Orientation = 5
            elseif k <= 1 and k > 0 then
                Orientation = 6
            elseif k <= 0 and k > -1 then
                Orientation = 7
            elseif k <= -1 then
                Orientation = 8
            end
        end
    end

    --获取对应方向参数（后续可以提到外面宏处理）
    local OrientationList = td.OrientationOrder[Orientation]
    local OrientationItem = {}
    for i, num in ipairs(OrientationList) do
        table.insert(OrientationItem,td.OrientationAll[num])
    end

    --后面和某函数类似，但是返回值和返回条件不一样
    local x_min = 1 local x_max = td.Map.num_x
    local y_min = 1 local y_max = td.Map.num_y     

    --使用记录,搜过的点记录在内，不管有没有覆盖到 ，
    local BFS = { }    --格式为二维数组 BFS[1][2] = true 为搜索中 false 为搜索完毕 
    local open = { }    --列表，按顺序进行一个个搜索
    local sum = {  } --用于记录所有满足条件的格点 { x = 1 , y = 2 , num = 1} x,y为格点坐标，num为距离

    for i=1,x_max do
        BFS[i] = { }
    end

    --子程序
    local function _OpenSpot(x,y,num) --开启搜索（添加到open列表）num表示距离，用于排序
        BFS[x][y] = true    --设置标识
        table.insert(open,{ gridX = x , gridY = y , num = num })
        table.insert(sum,{ gridX = x , gridY = y , num = num })
    end

    local function _CloseNowSpot()    --关闭搜索（移除open列表）
        BFS[open[1].gridX][open[1].gridY] = false   --设置标识
        table.remove(open,1)
    end
    --初始化
    local starNum 
    starPos = td.GetGridForPos(starPos)
    endPos = td.GetGridForPos(endPos)
    _OpenSpot(endPos.gridX,endPos.gridY,0)
    while true do
        if #open == 0 then break end       --如果没有open了则跳出循环

        local this = open[1]
        if this.gridX == starPos.gridX and this.gridY == starPos.gridY then starNum = this.num end
        if starNum and this.num > starNum then break end    --如果（最近的目标点）是自己现在的位置，则直接跳出

        --判定自己
        if Map[this.gridX] then 
            if Map[this.gridX][this.gridY] then  
                if #Map[this.gridX][this.gridY] == 0 then   -- 判定这个位置 如果没人则返回  
                    return { gridX = this.gridX, gridY = this.gridY }                    
                end
            else
                return { gridX = this.gridX, gridY = this.gridY }
            end
        else
            return { gridX = this.gridX, gridY = this.gridY }
        end

        for i,o in ipairs(OrientationItem) do   --宽搜
            local _x = o.x + this.gridX  
            local _y = o.y + this.gridY
            if _x >= x_min and _x <= x_max and _y >= y_min and _y <= y_max then --如果在地图内
                if BFS[_x][_y] == nil then
                    _OpenSpot(_x,_y,this.num+1) 
                end
            end
        end                

        _CloseNowSpot()    --移除自己
    end

--    dump(sum)
    return starPos
end

function td.SeekRoadFor4( star , radius , Map )  --四方向圆形四点判定：起点坐标，覆盖半径，地图数据 返回覆盖的格子
    --从起点开始，进行四向判定
    if true then -- radius <= td.Map.w/8 and radius <= td.Map.h/8  then  --范围远小于格子大小时不做判定直接返回
        return {{ x = star.gridX , y = star.gridY , num = 0 }}  --放回自己当前格子
    end 
    Map = Map or td.GridPos
--    dump(Map)
    local x_min = 1 local x_max = td.Map.num_x
    local y_min = 1 local y_max = td.Map.num_y

    local Orientation = {                      { x = 0 , y = 1 },
                            { x = -1 , y = 0 },                  { x = 1 , y = 0 },
                                               { x = 0 , y = -1},
                            }

    --使用记录,搜过的点记录在内，不管有没有覆盖到 ，
    local BFS = { }    --格式为二维数组 BFS[1][2] = true 为搜索中 false 为搜索完毕 
    local open = { }    --列表，按顺序进行一个个搜索
    local sum = {  } --用于记录所有满足条件的格点 { x = 1 , y = 2 , num = 1} x,y为格点坐标，num为距离

    for i=1,x_max do
        BFS[i] = { }
    end

    --子程序
    local function _OpenSpot(x,y,num) --开启搜索（添加到open列表）num表示距离，用于排序
        BFS[x][y] = true    --设置标识
        table.insert(open,{ x = x , y = y , num = num })
        table.insert(sum,{ x = x , y = y , num = num })
    end

    local function _CloseNowSpot()    --关闭搜索（移除open列表）
        BFS[open[1].x][open[1].y] = false   --设置标识
        table.remove(open,1)
    end
    --初始化
    star = td.GetGridForPos(star)
    _OpenSpot(star.gridX,star.gridY,0)
    while true do
        if #open == 0 then break end       --如果没有open了则跳出循环

        local this = open[1]
        for i,o in ipairs(Orientation) do   --宽搜
            local _x = o.x + this.x  
            local _y = o.y + this.y
            if _x >= x_min and _x <= x_max and _y >= y_min and _y <= y_max then --如果在地图内
                if BFS[_x][_y] == nil then                    --如果边缘触碰到了（原点+-半径)八重if判定
                    local _isOpen = false
                    --以降低30%精度判定为代价减少50%判定次数
                        if math.pow((Map[_x][_y].x_max+Map[_x][_y].x_core)*0.5-star.x,2) + math.pow((Map[_x][_y].y_min+Map[_x][_y].y_core)*0.5-star.y,2) <= radius * radius  then _isOpen = true
                    elseif math.pow((Map[_x][_y].x_max+Map[_x][_y].x_core)*0.5-star.x,2) + math.pow((Map[_x][_y].y_max+Map[_x][_y].y_core)*0.5-star.y,2) <= radius * radius  then _isOpen = true
                    elseif math.pow((Map[_x][_y].x_min+Map[_x][_y].x_core)*0.5-star.x,2) + math.pow((Map[_x][_y].y_min+Map[_x][_y].y_core)*0.5-star.y,2) <= radius * radius  then _isOpen = true
                    elseif math.pow((Map[_x][_y].x_min+Map[_x][_y].x_core)*0.5-star.x,2) + math.pow((Map[_x][_y].y_max+Map[_x][_y].y_core)*0.5-star.y,2) <= radius * radius  then _isOpen = true  end  
                    if _isOpen then _OpenSpot(_x,_y,this.num+1) end 

                end
            end
        end        

            --自己判定

        _CloseNowSpot()    --移除自己
    end
    return sum
end

function td.LookForNearestEnemy(star, radius, PointList , player ,type)    -- 给定指定格子范围，在范围内搜索最近的敌人,当前位置，仇恨范围，需要搜索的格子,当前玩家，搜索模式（0全部，1敌人,2队友）
    type = type or 1
    local enemy = nil
    local _num = 0
    local enemyList = { }
    for i, var in ipairs(PointList) do
        if var.num > _num then              -- 同一级级别距离的格子搜索完毕时
            if #enemyList == 0 then         -- 如果还没有搜索到人则搜索外一圈
                _num = _num + 1
            else break end                  -- 如果已经最近格子有敌人则停止继续搜索
        end
        -- 将所有同一级别距离的敌人整合判定
        local actorList = td.MapLayer:GetActorByPos(var)      -- 获取该格子的敌人，加入列表
        for t, actor in ipairs(actorList) do
            --根据type进行处理
            if type == 1 then 
                if actor._player ~= player and actor.isLive then           -- 排除掉自己和己方单位
                    table.insert(enemyList, actor)
                end
            elseif type == 2 then 
                if actor._player == player and actor.isLive then           -- 排除掉敌方单位
                    table.insert(enemyList, actor)
                end
            elseif type == 0 and actor.isLive then                             -- 不进行排除
                table.insert(enemyList, actor)
            end
            
        end
    end

    local hatred_min = radius * radius   --将最小距离默认设为仇恨范围 的平方

    for i, _enemy in ipairs(enemyList) do      -- 遍历，找出最近的敌人，设为仇恨目标
        local enemy_pos = _enemy:pos()
        local distance = ( star.x - enemy_pos.x ) * ( star.x - enemy_pos.x ) + ( star.y - enemy_pos.y ) * ( star.y - enemy_pos.y )
        if distance <= hatred_min then          -- 如果更近，则设为
            hatred_min = distance
            enemy = _enemy
        end
    end

    return enemy
end

function td.CollisionExclude()

end

function td.PointSlopeForm(data) --data.a_pos a点坐标 data.b_pos b点坐标 data.a_k a向量 返回交点坐标
    local a,b,k = data.a_pos ,data.b_pos ,data.a_k 
    
    if a==nil or b==nil or k==nil then return  end

    local a_x,a_y = a.x,a.y
    local b_x,b_y = b.x,b.y
    local a_kx,a_ky = k.x,k.y
    local a_k,b_k,c_x,c_y
    
    local a_kxy = cc.pNormalize({x=a_kx,y=a_ky})  --转换为单位向量
    a_kx,a_ky = a_kxy.x,a_kxy.y

    if a_kx == 0 then
--		print("斜率不存在")
		b_k = 0
		c_x = b_x
		c_y = a_y
	elseif a_ky == 0 then 
--		print("斜率为0")
		a_k = 0
		c_y = b_y
		c_x = a_x
	else
		a_k = a_ky/a_kx
		b_k = -1/a_k
		
		c_x = (a_k*a_x - a_y - b_k*b_x + b_y )/( a_k - b_k )
		c_y = a_k*(c_x-a_x)+a_y
	end

    return {x=c_x,y=c_y}
end


function td.test()  
    local x = {1,1,1,1,1}
    for i, var in ipairs(x) do
        x[i+1] = x[i] + 1
        if i>5 then dump(x) return end
    end
end